/*
 * @lc app=leetcode.cn id=877 lang=cpp
 *
 * [877] 石子游戏
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    // vector<int>* refPiles;
    bool stoneGame(vector<int>& piles) {
        // int first = 0, second = 0;
        // int left = 0, right = 0;
        // int n = piles.size();
        // bool firstTurn = true;
        // while (left+right != n){
        //     int greedy = 0;
        //     if (piles[left] > piles[n-1-right]){
        //         greedy = piles[left];
        //         ++left;
        //     }else{
        //         greedy = piles[n-1-right];
        //         ++right;
        //     }
        //     if (firstTurn){
        //         first += greedy;
        //     }else{
        //         second += greedy;
        //     }
        //     firstTurn = !firstTurn;

        //     printf("now %d %d turn %d l&r %d %d\n", 
        //     first, second, firstTurn, left, right);
        // }
        // return first > second;

        // 实际上先手必胜
        // return true;

        // greedy won't work in case [3,2,10,4]
        // hhhh
        // try dp & bfs
        // 开始想复杂了，dp实际上只需要存储当前先手所能拿的最高分
        // 因为当前选择人，无论是面对偶数个的先手还是面对级数的后手都会取最大解
        // 也无需分别存储先手后手得分，当前段之和减去最高即后手？？？
        // 真的是这样么，似乎这建立在理性人的条件之上。。。不过不用管这些了

        int n = piles.size();
        if (n == 2){return true;}

        // printf("n is %d\n", n);
        // refPiles = &piles;
        // vector<vector<int>> dp(n, vector<int>(n, 0));
        vector<vector<int>> dp;
        dp.resize(n);
        for (auto& item : dp){
            item.reserve(n);
        }
        // 2
        for (int i=0;i<n-1;++i){
            int a = piles[i];
            int b = piles[i+1];
            dp[i][i+1] = a>b?a:b;
            // printf("dp %d %d is %d\n", i, i+1, dp[i][i+1]);
        }
        // printf("n is %d\n", n);

        // 3
        // for (int j=0;j<n-2;++j){
        //     int a = piles[j] + (sum(j+1, j+1+ 3-1 ) - dp[j+1][j+1 +3-1 ]);
        //     int b = piles[j + 3-1] + (sum(j, j+ 3-1 ) - dp[j][j +3-1 ]);
        //     dp[j][j+2] = a>b?a:b;
        // }

        for (int length=3;length<n+1;++length){
            // printf("length %d\n", length);
            for (int j=0;j<n-length+1;++j){
                // printf("pile %d is %d, right sum %d to %d is %d, dp is %d\n",
                // j, piles[j], 
                // j+1, j+ length-1, sum(j+1, j+ length-1 , piles),
                // dp[j+1][j +length-1 ]
                // );
                int a = piles[j] + (sum(j+1, j+ length-1 , piles) - dp[j+1][j +length-1 ]);
                // printf("pile %d is %d, left sum %d to %d is %d, dp is %d\n",
                // j + length-1, piles[j + length-1], 
                // j, j+ length-1, sum(j, j+ length-2 , piles),
                // dp[j][j +length-2 ]
                // );
                int b = piles[j + length-1] + (sum(j, j+ length-2 , piles) - dp[j][j +length-2 ]);
                dp[j][j+length-1] = a>b?a:b;
                // printf("dp %d %d is %d\n", j, j+length-1, dp[j][j+length-1]);
            }
        }

        return dp[0][n-1]>sum(0, n-1, piles)-dp[0][n-1];
    }
    int sum(int begin, int end, vector<int>& piles){
        auto iterBegin = piles.begin() + begin;
        // iterBegin += begin;
        auto iterEnd = piles.begin() + end + 1;
        // iterEnd += end;
        return accumulate(iterBegin, iterEnd, 0);
    }
};
// @lc code=end
int main(){
    vector<int> myTest{5,3,4,5};
    Solution mySolution;
    mySolution.stoneGame(myTest);
    return 0;
}

// pointer to ref
// why error large
